//链表的回文结构
//思路二：快慢指针
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        if (!A || !(A->next))
            return true;
        //找中间节点
        ListNode* fast = A;
        ListNode* slow = A;
        ListNode* prev = NULL;
        while (fast && (fast->next)) {
            prev = slow;
            fast = fast->next->next;
            slow = slow->next;
        }
        //链表分割（A-->prev）
        prev->next = NULL;
        //链表逆置
        ListNode* next = NULL;
        ListNode* cur = slow;
        ListNode* tmp = NULL;
        while (cur) {
            next = cur->next;
            cur->next = tmp;
            tmp = cur;
            cur = next;
        }
        //tmp是slow后面链表逆置后的首节点
        while (A) {
            if (A->val != tmp->val)
                return false;
            else {
                A = A->next;
                tmp = tmp->next;
            }
        }
        return true;
    }
};